package program.heap;

import program.array.ArrayV2;

/**
 * 最大堆
 * 1. 任意节点不大于其父节点.
 * <p>
 * 底层数据结构: 使用动态数组
 * 使用数组来表示完全二叉树, 表示堆.
 * 从0开始, 保存数据.
 * <p>
 * 计算parent节点公式:　(index - 1) / 2;
 * left: 2 * i +　１;
 * right: 2 * i + 2;
 * <p>
 * add和extractMax的时间复杂度: O(logn).
 */
public class MaxHeap<E extends Comparable<E>> {

    private ArrayV2<E> data;

    public MaxHeap() {
        data = new ArrayV2<>();
    }

    public MaxHeap(int capacity) {
        data = new ArrayV2<>(capacity);
    }

    public int getSize() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * 向堆中添加元素data.
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 查看堆中最大元素.
     */
    public E findMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Heap is empty!");
        }

        return data.get(0);
    }

    /**
     * 取到堆中最大元素.
     * 思路:
     * 1. 0索引元素就是堆中最大元素.
     * 2. 把最后一个元素和0元素替换.
     * 3. 删除最大元素.
     * 4. 替换完之后, 可能堆的性质失效; 需要不断比对, 0元素和子元素的大小;
     */
    public E extractMax() {
        E ret = findMax();

        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    /**
     * 下沉:
     */
    private void siftDown(int k) {
        // 使用leftChild是原因在于, 使用了数组保存; leftChild的index总是小于rightChild的index;
        // 因此, 若leftChild的index已经大于数组的大小; 就代表k没有左右节点.
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                // data[j]是leftChild和rightChild中的最大值.
                // 也可以使用 j = j + 1;
                j = rightChild(k);
            }

            // k 大于j: 说明k不需要进行下浮, 当前就符合堆的特性.
            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }

            // k小于j, 需要交换k和j的位置.
            data.swap(k, j);
            // k为k和j中小的那个元素.
            k = j;
        }
    }

    /**
     * 上浮:
     * 因为是堆, 需要保持堆的性质(父节点总是大于子节点)
     */
    private void siftUp(int k) {
        // k的父亲节点若是小于子节点, 则需要交换父节点和子节点的位置.
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 返回完全二叉树的数组表示中, 一个索引所表示的元素的父亲节点的索引.
     *
     * @param index: 当前索引.
     * @return : 当前index的父亲节点.
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }

        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中, 一个索引所表示的元素的左节点的索引.
     *
     * @param index: 当前索引.
     * @return : 当前index的左节点.
     */
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    /**
     * 返回完全二叉树的数组表示中, 一个索引所表示的元素的右节点的索引.
     *
     * @param index: 当前索引.
     * @return : 当前index的右节点.
     */
    private int rightChild(int index) {
        return 2 * index + 2;
    }
}
